package com.xian;

/**
 * 测试斐波那契数列
 *  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946
 */
public class FBNCTest {
    public static void main(String[] args) {
       /* for (int i = 0; i<=9; i++) {
            System.out.printf("第%d个斐波那契数列为：%d"+System.lineSeparator(), i, fbnc1(i));
        }*/


        /*for (int i = 0; i<=9; i++) {
            System.out.printf("23第%d个斐波那契数列为：%d"+System.lineSeparator(), i, fbnc2(i));
        }*/

        //测试用时
        int n = 4; //获取第几个斐波那契数
        long startTime = System.currentTimeMillis();
        System.out.println(fbnc1(n));
        long endTime = System.currentTimeMillis();
        System.out.println("fbnc1用时(ms):"+(endTime-startTime));


        startTime = System.currentTimeMillis();
        System.out.println(fbnc2(n));
        endTime = System.currentTimeMillis();
        System.out.println("fbnc2用时(ms):"+(endTime-startTime));


    }

    /**
     * 采用递归方式   性能较差，数字大时会内存溢出
     * @param n
     * @return
     */
    public static long fbnc1(int n){
        if (n<=1)
            return n;
        return fbnc1(n-1) + fbnc1(n-2);
    }


    public static long fbnc2(int n){
        if (n<=1)
            return n;
        long first = 0;
        long secend = 1;

        for (int i =1; i<n; i++) {
            long current_num = first + secend;
            first = secend;
            secend = current_num;
        }

        return secend;
    }
}
